package hot100;


/*
 * Author：江松
 * Date：2023/4/13 10:48
 *
 *
 零钱兑换：
 完全背包问题
 dp(i,j)表示前i个物品中拿，组成j值，所需要的物品个数min
 */

public class Main322 {
    public int coinChange(int[] coins, int amount) {
        if(amount==0)return 0;
        int n=coins.length;
        int dp[][]=new int[n+1][amount+1];


        for(int i=1;i<=amount;++i)dp[0][i]=10005;

        for(int i=1;i<=n;++i){
            long w=coins[i-1];
            for(int j=0;j<=amount;++j){
                dp[i][j]=10005;
                for(int k=0;k*w<=j;++k){
                    int last=(int)(j-k*w);
                    dp[i][j]=Math.min(dp[i][j],dp[i-1][last]+k);
                }
            }
        }

        for(int i=0;i<=n;++i){
            for(int j=0;j<=amount;++j){
                System.out.printf("%-10d",dp[i][j]);
            }
            System.out.println();
        }
        return dp[n][amount]>amount?-1:dp[n][amount];

    }
}
